﻿#define _CRT_SECURE_NO_WARNINGS 1




//
//#include<iostream>
//#include<vector>
//#include<queue>
//
//using namespace std;
//
//typedef pair<int, int>PII;
//
//const int N = 1e5 + 10;
//
//int n, m;
//vector<PII>edges[N];
//
//bool st[N];//标记是否已经访问过
//
//
////dfs遍历
//void dfs(int u)
//{
//	cout << u << endl;
//	st[u] = true;
//
//	//遍历所有孩子
//	for (auto& t : edges[u])
//	{
//		//u->v的一条边，权值为w
//		int v = t.first, w = t.second;
//		if (!st[v])
//			dfs(v);
//	}
//}
//
//
////bfs遍历
//void bfs(int u)
//{
//	queue<int>q;
//	q.push(u);
//	st[u] = true;
//
//	while (q.size())
//	{
//		auto a = q.front();
//		q.pop();
//		cout << a << endl;
//		
//		for (auto& t : edges[a])
//		{
//			int b = t.first, c = t.second;
//			if (!st[b])
//			{
//				q.push(b);
//				st[b] = true;
//			}
//		}
//	}
//}
//
//
////和树的存储⼀模⼀样，只不过如果存在边权的话，我们的 vector 数组⾥⾯放⼀个结构体或者是 pair 即可。
//
//
//int main()
//{
//	cin >> n >> m;//读入结点个数以及边的个数
//	for (int i = 1;i <= m;i++)
//	{
//		int a, b, c;
//		cin >> a >> b >> c;
//		//a和b之间有一条边，权值为c
//		edges[a].push_back({ b,c });
//
//		//如果是无向边，需要反过来再存一下
//		edges[b].push_back({ a,c });
//	}
//
//	return 0;
//}